#include <stdio.h>
#include <stdlib.h>

// 树结点结构
struct TreeNode
{
    int value;              // 结点值（数组索引）
    struct TreeNode *left;  // 左子树（小于当前值）
    struct TreeNode *right; // 右子树（大于当前值）
};

// 创建新结点
struct TreeNode *createNode(int value)
{
    struct TreeNode *node = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    node->value = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 递归构建折半查找判定树
struct TreeNode *buildDecisionTree(int low, int high)
{
    if (low > high)
    {
        return NULL;
    }

    // 计算中间索引（决策点）
    int mid = low + (high - low) / 2;

    // 创建当前决策结点
    struct TreeNode *root = createNode(mid);

    // 递归构建左子树（左半部分）
    root->left = buildDecisionTree(low, mid - 1);

    // 递归构建右子树（右半部分）
    root->right = buildDecisionTree(mid + 1, high);

    return root;
}

// 打印树结构（前序遍历）
void printTree(struct TreeNode *root, int level)
{
    if (root == NULL)
        return;

    // 打印缩进
    for (int i = 0; i < level; i++)
    {
        printf("  ");
    }

    // 打印当前结点
    printf("|- Decision Point: %d\n", root->value);

    // 递归打印左子树
    printTree(root->left, level + 1);

    // 递归打印右子树
    printTree(root->right, level + 1);
}

// 主函数测试
int main()
{
    // 创建有序数组（大小为10）
    int arr_size = 10;

    printf("Building decision tree for binary search on array of size %d\n", arr_size);

    // 构建折半查找判定树（索引范围0-9）
    struct TreeNode *root = buildDecisionTree(0, arr_size - 1);

    // 打印决策树结构
    printf("\nBinary Search Decision Tree Structure:\n");
    printTree(root, 0);

    // 解释说明
    printf("\nNote: Each node represents a decision point (mid index) in binary search process.\n");
    printf("Left subtree: Search in left half (indices < current)\n");
    printf("Right subtree: Search in right half (indices > current)\n");

    return 0;
}